package lcr;

public class Test0102 {

    public static void main(String[] args) {
        new Solution0102_1().findTargetSumWays(new int[]{1,1,1,1,1},5);
    }
}

class Solution0102_1 {
    public int findTargetSumWays(int[] nums, int target) {
        int sum=0;
        for (int num : nums) sum+=num;
        int temp = sum - target;
        if (temp<0||(temp&1)!=0) return 0;
        temp>>=1;
        int[] dp = new int[temp+1];
        dp[0]=1;

        for (int num : nums) {
            for (int i = temp; i >= num; i--) {
                dp[i]+=dp[i-num];
            }
        }

        return dp[temp];
    }
}
